#include <iostream>
#include <vector>
#include<algorithm>

using namespace std;

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> ans;
        sort(nums.begin(), nums.end());
        for (size_t i = 0; i < nums.size() - 2 ; i++) {
            if (i > 0 && nums[i] == nums[i-1]) continue;
            if (nums[i] > 0) break;

            // Here, change the 2-for to 1-for by left and right pointer.
            int l = i + 1, r = nums.size() - 1;
            while (l < r) {
                if (l > i+1 && nums[l] == nums[l-1]) {
                    l++;
                    continue;
                }
                if (r < nums.size() - 1 && nums[r] == nums[r+1]) {
                    r--;
                    continue;
                }

                if (nums[r] < 0) break;

                int t = nums[i] + nums[l] + nums[r];
                if (t == 0) {
                    vector<int> v;
                    v.push_back(nums[i]);
                    v.push_back(nums[l]);
                    v.push_back(nums[r]);
                    ans.push_back(v);
                    l++;
                    r--;
                } else if (t < 0) {
                    l++;
                } else {
                    r--;
                }
            }
        }
        
        return ans;
    }
};


int main(void)
{
    printf("#15. 三数之和\n");
    vector<int> nums = {-1,0,1,2,-1,-4};

    vector<vector<int>> ans =  Solution().threeSum(nums);
    for (int i = 0; i < ans.size(); i++) {
        for (int j = 0; j < ans[i].size(); j++)
            cout << ans[i][j] << ", ";
        cout << endl;
    }
    return 0;
}